package com.leetcode;

/**
 * 1863. 找出所有子集的异或总和再求和
 * 一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
 * 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
 * 给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
 * 注意：在本题中，元素 相同 的不同子集应 多次 计数。
 * 数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
 * 1 <= nums.length <= 12
 * 1 <= nums[i] <= 20
 */
public class LeetCode1863 {


    public static int res = 0;

    public static void main(String[] arg0) {
        int[] nums = {3, 4, 5, 6, 7, 8};

        dfs(0, 0, nums);
        System.out.println("res: " + res);
    }


    /**
     * @param val 前一个子集的异或值
     * @param idx 当要处理的值，两种可能，不参与子集或参与子集
     * @param nums 数据值
     */
    public static void dfs(int val, int idx, int[] nums) {
        if (idx == nums.length) {
            res += val;
            return;
        }

        // 不参与子集
        dfs(val, idx + 1, nums);
        // 参与子集
        dfs(val ^ nums[idx], idx + 1, nums);
    }

}
